package prefix;

public class TrieByArray {

    public static void main(String[] args) {
        TrieByArray trie = new TrieByArray();
        trie.insert("abcd");
        trie.insert("abc");
        trie.insert("abc");
        System.out.println(trie.search("abbc"));
    }

    private final int MAXN = 150001;

    private final int[][] tree = new int[MAXN][26];

    private final int[] pass = new int[MAXN];
    private final int[] end = new int[MAXN];

    private int cnt;

    public TrieByArray() {
        this.cnt = 1;
    }

    public void insert(String word) {
        int cur = 1;
        pass[cur]++;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur]++;
        }
        end[cur]++;
    }

    public int search(String word) {
        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return end[cur];
    }

    public int prefixSearch(String prefix) {
        int cur = 1;
        for (int i = 0; i < prefix.length(); i++) {
            int path = prefix.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                return 0;
            }
            cur = tree[cur][path];
        }
        return pass[cur];
    }

    public void delete(String word) {
        if (search(word) == 0) {
            return;
        }

        int cur = 1;
        for (int i = 0; i < word.length(); i++) {
            int path = word.charAt(i) - 'a';
            if (--tree[cur][path] == 0) {
                tree[cur][path] = 0;
                return;
            }
        }
        end[cur]--;

    }

}
